package com.person.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18.四数之和
 * 2022-06-10 16:25:55
 **/
public class Sequence_0018_FourSum {
    public static void main(String[] args) {
        Solution solution = new Sequence_0018_FourSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            int len = nums.length;
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            if (len < 4) {
                return ans;
            } else {
                //a < b < c < d
                int a = 0, b = 1, c = 2, d = len - 1;
                for (; a < len - 3; a++) {
                    if (a > 0 && nums[a] == nums[a - 1]) {
                        continue;
                    }
                    for (b = a + 1; b < len - 2; b++) {
                        if (b > a + 1 && nums[b] == nums[b - 1]) {
                            continue;
                        }
                        for (c = b + 1; c < len - 1; c++) {
                            if (c > b + 1 && nums[c] == nums[c - 1]) {
                                continue;
                            }
                            for (d = len - 1; d > c; d--) {
                                if (d < len - 1 && nums[d] == nums[d + 1]) {
                                    continue;
                                }
                                int sum = nums[a] + nums[b] + nums[c] + nums[d];
                                if (sum < target) {
                                    break;
                                } else if (sum == target) {
                                    Integer[] arr = {nums[a], nums[b], nums[c], nums[d]};
                                    ans.add(Arrays.asList(arr));
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}